package tree;

import java.util.HashMap;
import java.util.Map;

/**题目：用二叉树的前序和中序构建二叉树
 * @Author Gavin
 * @date 2022.01.03 15:58
 */
public class tree_13 {

    private TreeNode buildTree(int[] pre, int preStart, int preEnd,
                               int inStart, Map<Integer,Integer> inPos){
        if(preStart>preEnd)return null;
        TreeNode root=new TreeNode(pre[preStart]);
        int rootIdx=inPos.get(pre[preStart]);//获取前序中根节点在中序遍历中的位置
        int leftLen=rootIdx-inStart;//得到左子树元素的个数
        /**
         * preStart+leftLen 的值有点迷惑人  leftLen是实际的个数，并不是数组的下标，所以按个数来对应数组下标
         * 的话会比下标多1，所以这个值preStart+leftLen的值对应的下标实际上就是根节点对应的下标值，所以正常来说
         * 我们不应该要根节点，实际上这里不要把这个值当作数组下标来使用，而是要当作节点个数来使用，可以解释为：preStart对应的
         * 为根节点，根节点的左节点个数为leftLen，所以新的左子数的个数的preEnd就为preStart(开始的下标)+leftLen（左字数的个数）
         * 就为新的左字数的preEnd对应的下标
         */
        root.left=buildTree(pre,preStart+1,preStart+leftLen,inStart,inPos);
        root.right=buildTree(pre,preStart+leftLen+1,preEnd,rootIdx+1,inPos);
        return root;
    }

    /**
     * 前序遍历为：根左右
     * 中序遍历为：左根右
     *
     * 首先用前序的第一个节点作为根节点在中序遍历种已
     * 这个节点把中序序列分割为左子树和右子树
     */
    //Time:O(n) Space:O(n)
    public TreeNode solution(int[] pre,int[] in){
        //首先把中序序列的元素和下标存入到hashmap中
        Map<Integer,Integer> inPos=new HashMap<>();
        for (int i = 0; i < in.length; i++) {
            inPos.put(in[i],i);
        }
        return buildTree(pre,0,pre.length-1,0,inPos);
    }
}
